package com.gxc.recursion;

/**
 * 用zigzag的方式打印矩阵，比如如下的矩阵
 * 0  1  2  3
 * 4  5  6  7
 * 8  9  10 11
 * 打印顺序为:0 1 4 8 5 2 3 6 9 10 7 11
 *
 * 解法：
 * 设置两个指针，
 * 一个开始一直向右走，碰到右边界则向下走
 * 另一个开始一直向下走，碰到下边界则向右走
 */
public class Zigzag {

    public static void main(String[] args) {
        int[][] array = generate();

        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println("");
        }

        System.out.println("---------");
        System.out.print(array[0][0] + " ");
        zigzagPrint(array, 0, 1 , 1, 0,true);
        System.out.println("---------");
        zigzagPrint2(array);
    }


    /**
     *
     * @param array
     * @param rightX
     * @param rightY
     * @param lowX
     * @param lowY
     * @param slant  true  / 向下打印  false  /  向上打印
     */
    public static void zigzagPrint(int[][] array, int rightX, int rightY, int lowX, int lowY, boolean slant) {
        if (rightX == lowX && rightY==lowY) {
            System.out.print(array[rightX][rightY]);
            return;
        }

        int rightR = rightX;
        int rightC = rightY;
        int lowR = lowX;
        int lowC = lowY;

        if (slant) {
            while (rightX<=lowX) {
                System.out.print(array[rightX++][rightY--] + " ");
            }
        } else {
            while (rightX<=lowX) {
                System.out.print(array[lowX--][lowY++] + " ");
            }
        }
        if (rightC < array[0].length-1) {
            rightC++;
        } else {
            rightR++;
        }
        if (lowR < array.length-1) {
            lowR++;
        } else {
            lowC++;
        }
        slant = !slant;

        zigzagPrint(array, rightR, rightC, lowR, lowC, slant);
    }

    private static void zigzagPrint2(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0)
        {
            return;
        }
        int rdR = 0;
        int rdC = 0;
        int drR = 0;
        int drC = 0;
        int row = matrix.length;
        int col = matrix[0].length;
        boolean fromUp = false;  //控制打印方向
        while (rdR < row)
        {
            printDiagonal(matrix, rdR, rdC, drR, drC, fromUp);
            rdR += rdC == col - 1 ? 1 : 0;
            rdC += rdC == col - 1 ? 0 : 1;
            drC += drR == row - 1 ? 1 : 0;
            drR += drR == row - 1 ? 0 : 1;
            fromUp = !fromUp;  //每次打印完方向改变
        }
    }

    private static void printDiagonal(int[][] matrix, int rdR, int rdC, int drR, int drC, boolean fromUp) {
        if (fromUp)  //从右上角到左下角打印
        {
            while (rdR != drR + 1)
            {
                System.out.print(matrix[rdR++][rdC--] + " ");
            }
        }
        else
        {
            while (drR != rdR - 1)  //从左下角到右上角打印
            {
                System.out.print(matrix[drR--][drC++] + " ");
            }
        }
    }

    private static int[][] generate() {
        int[][] a = new int[3][4];

        int start = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                a[i][j] = start;
                start++;
            }
        }

        return a;
    }
}
